A variety of tools and technologies are presently available for navigating in geographical spaces. Global Positioning System (GPS) is a well known technology that finds prevalent use in navigating in geographical spaces. Cellular triangulation is another technology that is used either as an assistive method to GPS navigation or as a stand-alone method for navigation.
Navigating in geographical spaces essentially uses two things—a map of the geographical space, and a location of the navigation device in that map. Generally, a map database provides the map data for the first part, and GPS or other technology provides the navigating device's location relative to that map data.
Geographical spaces include boundaries. These boundaries are defined in a variety of ways. For example, countries have boundaries or borders relative to other countries. Similarly, states or provinces within a country have boundaries with other states or provinces. Likewise, cities, town, and suburbs have boundaries. Airspace boundaries exist in the air and maritime boundaries exist in navigable waters.
Furthermore, the boundaries can be interpreted in other ways as well. For example, the premises of a sporting arena have a boundary, a perimeter of a building is a boundary, and an area within a building also has boundary.
Some boundaries are visible to humans, and other boundaries are not. For example, a boundary on land between countries can be visibly marked with physical markers, or can be unmarked and therefore invisible. A boundary in a water body is often not marked with visible markers. Vast land areas including several real properties may not have visible markings demarcating one property from another.
Map data presently represents some such boundaries, including some visible boundaries and some invisible boundaries from a given geographical space. For example, maps show continuous boundaries between countries, over land, in water, and in the air, regardless of whether corresponding boundaries are physically marked in the corresponding geographical space.
While three dimensional (3D) maps and routes can be formed to represent a 3D geographical space, the illustrative embodiments are described using the most commonly used two dimensional (2D) maps of 3D geographical spaces. Such 2D maps represent 3D objects as 2D outlines. For example, 3D spaces are represented as 2D areas, and 3D structures, such as towers or hills, are represented as points, lines, or areas in the 2D map.
A common use of presently available map data is in computing a travel route from point A to point B in the geographical space. Presently, a map application identifies points A and B on a map and computes a route to navigate from A to B on that map using the routing elements defined in the map data. For example, a road is a routing element and is often represented as a line on a map. A route computed by a presently used map application attempts to use routing elements such as known roads, paths, highways, streets, and intersections thereof, to connect point A to point B. The routing elements selected by the map application can be constrained based on the mode of transportation used, and other conditions such as traffic, toll, speed limits, and the like.
The illustrative embodiments recognize that this method of finding routes works so long as points A and B are on a routing element. Often, a routing solution is needed between points A and B where either point A (the start or the origination), or point B (the end or the destination), or both are not on a routing element, i.e., to overlapping with a routing element.
The illustrative embodiments recognize that such situations are very common in day to day navigation using a map application. For example, a user commonly asks for a routing from the user's current location to a destination. The user may not be on a routing element, e.g., a road, but out in a field that is at some distance from a routing element. In many cases, destination also may not be on a routing element but in another area of the map that is not occupied by a routing element, and at some distance from the nearest routing element.
Hereinafter, a point that lies on a routing element of a map is called a “mapped point” or “MP”, and a point that lies in an area of the map that is not occupied by a routing element is called a “not mapped point”, and is referred to herein interchangeably as “NMP” or “NOTMP” or “NOT MP”. When either point A, or point B, or both are NMPs, different map applications handle the routing differently. For example, some presently used map applications will only route from an MP to another MP.
Some other routing applications do route from an NMP to an MP, or an NMP to an NMP, or an MP to an NMP. For example, such a routing solution draws a line between a starting NMP to the nearest beginning MP, generate the route from that beginning MP to another ending MP nearest to a destination NMP, and draw another line from the ending MP to the destination NMP.
FIGS. 1A, 1B, 1C, and 1D show some examples of the routes generated by prior art map applications. In FIG. 1A, NMP 151 is connected to MP 152, MP 152 is connected to MP 153, and MP 153 is connected to NMP 154. Route section 155 is a line of the shortest distance between NMP 151 and MP 152. Similarly, route section 156 is a line of the shortest distance between MP 153 and NMP 154.
In FIG. 1B, NMP 161 is connected to MP 162, MP 162 is connected to NMP 163. Route section 164 is a line of the shortest distance between NMP 161 and MP 162. Similarly, route section 165 is a line of the shortest distance between MP 162 and NMP 163.
In FIG. 1C, NMP 171 is connected to MP 172, MP 172 is connected to MP 173, and MP 173 is connected to NMP 174. Route section 175 is a line of the shortest distance between NMP 171 and MP 172. Similarly, route section 176 is a line of the shortest distance between MP 173 and NMP 174.
In FIG. 1D, NMP 181 is connected to MP 182, MP 182 is connected to NMP 183. Route section 184 is a line of the shortest distance between NMP 181 and MP 182. Similarly, route section 185 is a line of the shortest distance between MP 182 and NMP 183.
The routings of FIGS. 1A-D have been actually produced from presently available map applications. The illustrative embodiments recognize that in producing routings of FIGS. 1A-D, the prior-art map applications have failed to account for geographical constraints present in the geographical space where the route has to be navigated. A geographical constraint is a feature on a map that cannot be crossed by the selected mode of transportation in an actual geographical space but is not marked in the map data to avoid routing through it. Hereinafter, such geographical constraint is called a “not crossable element” or “NCE”. An NCE may correspond to an area, a line or a point on a 2D map that rendered from a given map data and is not precluded for routing or crossing in the map data.
For example, in FIG. 1B, route section 164 requires the navigation to occur across a water body, which is an example of an NCE. As another example, in FIG. 1C, route section 175 requires the navigation to occur across a highway, which is another example of an NCE. As another example, in FIG. 1D, route section 184 requires the navigation to occur across a railway track, which is another example of an NCE.
Thus, the illustrative embodiments recognize that the presently available map applications and other routing solutions fail to recognize these NCEs and other similar geographical constraints through which navigation should not occur for practical reasons. As a result, the routing produced from such map applications and other routing solutions are often impractical, dangerous, or simply not useful to a user given the geographical constraints the user is facing in the geographical space.